Network elements (NEs) use buffer memories, queues or FIFO's (collectively referred here as queues) for temporarily storing data units (referred here as packets) while the node processes the packet headers and executes other appropriate actions. Queues are also used to regulate the flow of packets between two nodes or between two stages of modules which make up a node or nodes. The transfer of data packets between the NEs or within a NE is regulated by using available FIFO space upstream of a congested stage to temporarily store packets intended for it. The queues must, however, be managed properly so that they do not overflow or underflow. For example, when a queue receives packets faster than it can dispose of them, the packets build up in the queue, resulting in a queue overflow. On the other hand, when the queue receives packets slower than it is capable of draining, a starved queue or a queue underflow results. In either situation, the performance of the network suffers.
A flow control mechanism between two consecutive queues is therefore needed to prevent overflow or underflow. In general, a flow control signal is a binary signal transmitted periodically from the downstream queue to the upstream queue to enable (Go) or disable (Stop) transmission of the next packet from the upstream queue. Such a flow control signal is typically referred to as a backpressure control signal. FIG. 1 shows a very simple illustration of two stages 10 and 12 along a certain connection established over a data network, where the packets are queued for processing and regulating the flow speed according to the QoS for the respective connection.
The stages 10, 12 may be provided on a same card (e.g. on a linecard, or on a switch fabric card, etc), on the same NE, or on distinct NE's; FIG. 1 provides just an example. Each stage uses a respective queue 2, 4. For the traffic direction shown in FIG. 1 (let's call it forward direction), queue 2 is the upstream queue which transmits packets at controlled intervals of time, and queue 4 is the downstream queue, which receives the packets from queue 2. It is to be noted that the upstream queue 2 at the upstream stage 10 is shown only by way of example; the packets may be delivered to downstream queue 4 by any traffic management device backpressured by mechanism 5 provided at the downstream stage 12.
Transmission of packets from queue 2 is controlled by a queue controller 3 at the upstream stage, while a backpressure mechanism 5 at the downstream stage checks the congestion status of queue 4. We denote with C the maximum rate (e.g., bits/sec, bytes/sec, cells/sec, etc) at which packets arrive to the second stage 12 into downstream queue 4; we also assume that the maximum transmit rate downstream from stage 12 is also C. In order to regulate the flow rate, backpressure mechanism 5 compares the queue occupancy Q with a configured threshold F. If the queue occupancy Q exceeds the threshold (Q>F), the backpressure control signal generated by unit 5 instructs controller 3 to temporarily stop transmission of packets from queue 2. If the queue occupancy Q is less than the threshold F (Q<F), the backpressure mechanism 5 instructs controller 4 to continue transmission of packets from queue 2 to queue 4.
However, the backpressure control signal cannot stop the data flow instantaneously, so that queue 4 continues to receive packets for a certain amount of time T called “round trip time”. The round trip time is determined as the sum of the maximum latency from the point in time that a queue threshold F is crossed to the point in time that the first stage 10 stops sending traffic to that queue, denoted with T1, plus the maximum time T2 a packet needs for transfer between the output of the first stage queue 2 to the second stage queue 4. In other words, T=T1+T2.
The value of T for a high speed router is on the order of multiple microseconds. The value of C for a high speed router is on the order of ten Gbps. As a result, several Mbits of storage are required in the second stage device for ensuring a proper flow rate. In some cases, for a given architecture, a large round trip time T or a small storage capacity at the second stage may require an intermediate queuing stage between first stage 10 and second stage 12. On occasions, this scenario may possibly affect feasibility of a given system design.
In addition, a large round trip time results in the need to design larger FIFOs, for storing the packets arrived after the threshold has been crossed. This situation is particularly relevant to synchronization of line side traffic at the output of stage that uses FIFOs (e.g. on a line card, a framer).
Furthermore, in order to minimize cost and board area, the second stage device storage is ideally internal to the device. The number of queues in a NE device may be very large. For example, if the second stage is a fabric interface device, it may contain several hundred queues, so that the queues consume a very large amount of memory. If we take into account the round trip time T, the downstream queue needs to store more data on a per physical port basis. Therefore, it is important to find a way of reducing the storage requirement in the second stage device.
U.S. Patent Application (Sterne et al.) Publication number 20040257991, entitled “Backpressure history mechanism in flow control” discloses a mechanism for monitoring the amount of traffic which is on the way toward the downstream queue during the past period of the round trip time. In this way, a more precise control of the traffic flow is possible, realizing reduction of storage space in the queue by one half. Preferably, a historical record of flow control signals sent back during the most recent flow control round trip time is kept and updated for further enhancing the flow control. While this U.S. Patent Application addresses the same problem as the present invention, it provides an entirely different solution.
U.S. Pat. No. 6,396,809 (Holden et al.), entitled “Method for signaling in a high speed communication system” and U.S. Pat. No. 6,973,032 (Casley et al.) entitled “Selective backpressure control for multistage switches” describe several variations of backpressure schemes. However, none of these patents uses a pulsed backpressure mechanism as in the present invention.